/* 
241. 为运算表达式设计优先级
*/
/**
 * @param {string} expression
 * @return {number[]}
 */

/* 
    分治算法:将原问题分解成小规模的子问题，然后根据子问题的结果构造出原问题的答案
    (大家了解的归并排序就是典型的使用分治思想)
    

*/
const memo = new Map()
var diffWaysToCompute = function (expression) {
    /* 避免重复计算 */
    if (memo.has(expression)) return memo.get(expression)
    let res = []
    for (let i = 0; i < expression.length; i++) {
        let c = expression.charAt(i)
        /* 扫描算式 expression 中的运算符 */
        if (c == "*" || c == "+" || c == "-") {
            /* 分 */
            let left = diffWaysToCompute(expression.slice(0, i))
            let right = diffWaysToCompute(expression.slice(i + 1))
            /* 
                治 
                通过子问题的结果,合成原问题的结果
            */

            for (let a of left) {
                for (let b of right) {
                    switch (c) {
                        case "*":
                            res.push(a * b)
                            break
                        case "+":
                            res.push(a + b)
                            break
                        case "-":
                            res.push(a - b)
                            break
                    }
                }
            }

        }
    }

    /* 
        base case 递归函数必须有个 base case 用来结束递归
        其实这段代码就是我怕么分治算法的base case 代表着你[分] 什么时候开始[治]
        如果 res 为空，说明算式是一个数字，没有运算符(因为当算式中不存在算式符的时候)
        就不会触发if 语句 也不会给res 添加任何 元素
    */
    if (!res.length) {
        res.push(parseInt(expression))
    }
    memo.set(expression, res)

    return res
};